package java.util;

import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.Serializable;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;

import sun.misc.SharedSecrets;


/**
 * 这里面只保留了put相关的方法，其他的方法没保存
 * <p>
 * 构造函数只留了一个空参构造
 *
 * @param <K>
 * @param <V>
 */
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {

  /**
   * 默认的初始容量—必须是2的幂。    默认 1 << 4 = 16
   */
  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  /**
   * 最大容量  必须是 2 的幂  最大值    1 << 30 = 2^30 = 1,073,741,824
   */
  static final int MAXIMUM_CAPACITY = 1 << 30;
  /**
   * 负载因子   0.75  数组长度的0.75开始扩容
   */
  static final float DEFAULT_LOAD_FACTOR = 0.75f;
  /**
   * 链表转红黑数的最小长度   >= 8
   */
  static final int TREEIFY_THRESHOLD = 8;
  /**
   * 红黑树转链表的长度    <= 6
   */
  static final int UNTREEIFY_THRESHOLD = 6;
  /**
   * 链表转红黑树的数组长度  >= 64
   */
  static final int MIN_TREEIFY_CAPACITY = 64;


  private static final long serialVersionUID = 362498820763181265L;
  /**
   * 哈希表的加载因子
   *
   * @serial
   */
  final float loadFactor;

  /* ---------------- Static utilities -------------- */
  /**
   * node 节点，在第一次使用时初始化，并根据需要调整大小。在分配时，长度总是2的幂。(我们也允许在一些操作中长度为0，以允许当前不需要的引导机制。)
   */
  transient Node<K, V>[] table;
  /**
   * 保存缓存entrySet()。注意，AbstractMap字段用于keySet()和values()。
   */
  transient Set<Map.Entry<K, V>> entrySet;
  /**
   * 这个映射中包含的键值映射的数量
   */
  transient int size;
  /**
   * 结构化修改是指改变HashMap中映射的数量或修改其内部结构(例如，rehash)。
   * 该字段用于使HashMap的集合视图上的迭代器快速失败。(见ConcurrentModificationException)。
   * <p>
   * 记录这个hashMap的修改次数，线程不安全
   */
  transient int modCount;


  /**
   * 构造一个空的<tt>HashMap<tt>，使用默认的初始容量(16)和默认的负载因子(0.75)。
   */
  public HashMap() {
    //所有其他字段均为默认值
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
  }




  /**
   * put 方法首先走这里
   *
   * @param key   key
   * @param value value
   * @return value
   */
  public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
  }

  /**
   * 前提知识点：java中计算的 hashCode 是一个int值，int值占4个字节，每个字节8个字符，共占32个字符
   * <p>
   * 采用高低16位异或算法 ， 计算key在数组存放的位置
   */
  static final int hash(Object key) {
    int h;
    // 如果这个key是null，直接将这个key存放在数组 0 索引 , 否则进行高低16位异或算法
    // key.hashCode() 计算出hash值，例如 1 的hash值是   0000 0000 0000 0000 0000 0000 0000 0001
    // h >>> 16       无符号右移16位，高位补0之后的值是   0000 0000 0000 0000 0000 0000 0000 0000
    // 计算出来的值是                                  0000 0000 0000 0000 0000 0000 0000 0001  表示 1 ,放在 1 索引
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

  /**
   * put 方法
   * <p>
   * 注释 1-1 表示第1次循环 key 为 1  ，  3-17 表示 第3次循环 ， 值为 17
   *
   * @param hash         数组中需要存放的数组下标
   * @param key          key
   * @param value        value
   * @param onlyIfAbsent 默认为false
   * @param evict        默认为true
   * @return previous value, or null if none
   */
  final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // 存放元素的数组
    Node<K, V>[] tab;
    // 当前hash值的索引出存放的node值
    Node<K, V> p;
    int n, i;  // 默认为 0
    // 1-1  条件成立表示是第一次添加
    if ((tab = table) == null || (n = tab.length) == 0) {
      // 1-1 创建一个新数组 赋值给 tab，并将新数组的长度赋值给 n ，此时 n = 16
      n = (tab = resize()).length;
    }
    // 1-1   (n - 1) & hash 表示 15 & 1 = 1 ，获取数组1索引的元素，如果为null，直接放进去
    if ((p = tab[i = (n - 1) & hash]) == null) {
      // 创建一个新的 node 单向链表，将链表存放在数组1索引处
      tab[i] = newNode(hash, key, value, null);
    } else {
      // 不是空的，出现了Hash冲突
      // 默认为 null ， 出现hash冲突并且key相同就会变成当前索引的node值
      Node<K, V> e;
      K k;

      //  p.hash == hash 出现Hash冲突  、
      //  ((k = p.key) == key || (key != null && key.equals(k))) 当前hash值的索引处的key又和传进来的key相等
      if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
        // 将原来的node拿出来
        e = p;
      } else if (p instanceof TreeNode) {
        e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
      } else {
        //  死循环处理，在每个下标处都寻找一下
        // 3-17 出现hash冲突，但是key不存在
        for (int binCount = 0; ; ++binCount) {
          // 3-17 如果hash冲突处的下一个节点是空的（链表长度为1）
          if ((e = p.next) == null) {
            // 3-17 将新来的元素挂到链表的下一个值里面
            p.next = newNode(hash, key, value, null);
            // 3-17 如果循环的次数 >= 7次 不成立
            if (binCount >= TREEIFY_THRESHOLD - 1) { // -1 for 1st
              // 链表转红黑树
              treeifyBin(tab, hash);
            }
            break;
          }
          if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            break;
          }
          p = e;
        }
      }

      // 如果 e不是空的，表示此处出现hash冲突并且key相同
      if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null) {
          // 替换原来的值为传进来的值
          e.value = value;
        }
        afterNodeAccess(e);
        // 返回原来的值
        return oldValue;
      }
    }
    // 修改次数+1
    ++modCount;
    // map的长度 +1 ，并判断是否超过加载因子
    if (++size > threshold) {
      // 13-13 当前长度为13，超过了阈值，扩容处理
      resize();
    }
    // 这个方法是空实现， LinkedHashMap 会实现这个方法，不管
    afterNodeInsertion(evict);
    return null;
  }

  /**
   * 初始化map的数组大小
   *
   * @return the table
   */
  final Node<K, V>[] resize() {
    // 将原有的 table 记录为 oldTab
    Node<K, V>[] oldTab = table;
    // 原来的数组的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 原来 扩容的阈值
    int oldThr = threshold;
    // newCap 新数组长度  newThr 新的阈值
    int newCap, newThr = 0;
    // 13-13 超过阈值，现在 oldCap 是16 ，直接进去
    if (oldCap > 0) {
      // 13-13 判断有没有超过数组最大值
      if (oldCap >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
        // 13-13 新的数组长度是老的基础上左移一位(*2),并且老的长度 必须 >= 16
      } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {
        // 阈值同样左移一位
        newThr = oldThr << 1; // double threshold
      }
    } else if (oldThr > 0) { // initial capacity was placed in threshold
      // 扩容的阈值 > 0 , 直接赋值
      newCap = oldThr;
    } else {               // zero initial threshold signifies using defaults
      //1-1 没有设置数组长度， 直接设置默认值 ， 数组长度为16，扩容阈值为12
      newCap = DEFAULT_INITIAL_CAPACITY;
      newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
      // 如果新的 阈值为0，使用 新的数组长度 * 0.75 计算出新的阈值，
      // 判断新的阈值有没有超过最大数组长度，超过最大使用最大的长度，否则使用新的阈值
      float ft = (float) newCap * loadFactor;
      newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
        (int) ft : Integer.MAX_VALUE);
    }
    // 替换原有的阈值
    threshold = newThr;
    // 通过新的长度计算创建出一个数组
    @SuppressWarnings({"rawtypes", "unchecked"})
    Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
    // 使用新的数组替换原有的数组
    table = newTab;
    // 13-13 扩容处理
    if (oldTab != null) {
      // 13-13 循环老数组长度的次数
      for (int j = 0; j < oldCap; ++j) {
        //13-13 存放当前索引上面的值
        Node<K, V> e;
        //13-13 如果当前索引有值
        if ((e = oldTab[j]) != null) {
          //13-13 将索引处元素置位null
          oldTab[j] = null;
          //13-13 表示链表下面没有元素了
          if (e.next == null) {
            //13-13 创建一个新的数组，将当前索引上的值放到 新的数组指定索引处（新的索引 = 新的hash & 新数组长度）
            newTab[e.hash & (newCap - 1)] = e;
          } else if (e instanceof TreeNode) {
            ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
          } else { // preserve order
            //链表下面还有元素， 现在有 1 和 17
            //存储与旧索引的相同的节点
            Node<K, V> loHead = null, loTail = null;
            //存储与新索引相同的节点
            Node<K, V> hiHead = null, hiTail = null;
            // 下一个节点的元素
            Node<K, V> next;
            // 拿出旧链表下面的元素
            do {
              // 将下一个值赋值给 next
              next = e.next;
              // 进到这里表示这个元素是链表的第一个值
              if ((e.hash & oldCap) == 0) {
                // 如果第一个值是空的，将当前元素给第一个，否则给到下一个
                if (loTail == null) {
                  loHead = e;
                } else {
                  loTail.next = e;
                }
                loTail = e;
              } else {
                if (hiTail == null) {
                  hiHead = e;
                } else {
                  hiTail.next = e;
                }
                hiTail = e;
              }
            } while ((e = next) != null);
            //通过判定将旧数据和新数据存储到新表指定的位置
            if (loTail != null) {
              loTail.next = null;
              newTab[j] = loHead;
            }
            if (hiTail != null) {
              hiTail.next = null;
              newTab[j + oldCap] = hiHead;
            }
          }
        }
      }
    }
    return newTab;
  }

  /**
   * 转红黑树的逻辑
   */
  final void treeifyBin(Node<K, V>[] tab, int hash) {
    int n, index;
    Node<K, V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
      resize();
    } else if ((e = tab[index = (n - 1) & hash]) != null) {
      TreeNode<K, V> hd = null, tl = null;
      do {
        TreeNode<K, V> p = replacementTreeNode(e, null);
        if (tl == null) {
          hd = p;
        } else {
          p.prev = tl;
          tl.next = p;
        }
        tl = p;
      } while ((e = e.next) != null);
      if ((tab[index] = hd) != null) {
        hd.treeify(tab);
      }
    }
  }


  /**
   * 创建一个新的节点
   */
  Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
    return new Node<>(hash, key, value, next);
  }

  /**
   * node节点 ， 里面包含 hash值，key ，value 和下一个节点
   * 删除了 一些不重要我的
   */
  static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

  }


}
